package second.codeTop.package1;

/**
 * @ClassName LC42
 * @description: 连续子数组的最大和
 * @author: 荣燊
 * @create: 2022-03-02 14:03
 **/
public class LC42 {
    public static void main(String[] args) {
        int[] test = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(test));
    }

    // 注意是连续的子数组
    // df[i] = max{df[i-1]+nums[i], nums[i]}
    public static int maxSubArray(int[] nums) {
        int pre = nums[0];
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            pre = Math.max(pre+nums[i], nums[i]);
            max = Math.max(pre, max);
        }
        return max;
    }
}
